package leetcode_2501_2600;

public class LeeCode_2516 {
    public static void main(String[] args) {
        System.out.println(takeCharacters("aabaaaacaabc", 2));
//        System.out.println(takeCharacters("a", 1));
//        System.out.println(takeCharacters("abc", 1));
        System.out.println(takeCharacters("acbcc", 1));
    }
    private static int takeCharacters(String s, int k) {
        int n = s.length();
        int l = -1;
        int rca = 0, rcb = 0, rcc = 0, r = n;
        int lca = 0, lcb = 0, lcc = 0;
        while (rca < k || rcb < k || rcc < k){
            r--;
            if (r < 0)
                break;
            if (s.charAt(r) == 'a'){
                rca++;
            }else if (s.charAt(r) == 'b'){
                rcb++;
            }else {
                rcc++;
            }
        }
        if (r < 0)
            return -1;
        int ans = n - r;
        while (l < n && r < n){
            l++;
            if (s.charAt(l) == 'a'){
                lca++;
            }else if (s.charAt(l) == 'b'){
                lcb++;
            }else {
                lcc++;
            }
            if (l == r){
                if (s.charAt(r) == 'a'){
                    rca--;
                }else if (s.charAt(r) == 'b'){
                    rcb--;
                }else {
                    rcc--;
                }
                r++;
            }
            int ga = Math.max(0, k - lca), gb = Math.max(0, k - lcb), gc = Math.max(0, k - lcc);
            while (rca >= ga && rcb >= gb && rcc >= gc && r < n){
                if (s.charAt(r) == 'a'){
                    rca--;
                }else if (s.charAt(r) == 'b'){
                    rcb--;
                }else {
                    rcc--;
                }
                r++;
            }
            if (r < n){
                r--;
                if (s.charAt(r) == 'a'){
                    rca++;
                }else if (s.charAt(r) == 'b'){
                    rcb++;
                }else {
                    rcc++;
                }
            }
            int tn = r;
            if (r == n){
                if (ga != 0 || gb != 0 || gc != 0){
                    tn--;
                }
            }
            ans = Math.min(ans, l + 1 + n - tn);
        }
        return ans;
    }
}
